package BackTrack.Medium;

public class LC0079 {
    char[][] board;
    String word;
    int[][] deltas = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        visited = new boolean[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (word.length() == 1) return true;
                    visited[i][j] = true;
                    if (innerRecursive(i, j, 1)) return true;
                    visited[i][j] = false;
                }
            }
        }

        return false;
    }

    private boolean innerRecursive(int i, int j, int ptr) {
        for (int[] delta : deltas) {
            int x = i + delta[0];
            int y = j + delta[1];
            if (x >= 0 && x < board.length && y >= 0 && y < board[0].length &&
                    board[x][y] == word.charAt(ptr) && !visited[x][y]) {
                if (ptr == word.length() - 1) return true;
                visited[x][y] = true;
                if (innerRecursive(x, y, ptr + 1)) return true;
                visited[x][y] = false;
            }
        }

        return false; // 当前位置开始不可能找到word
    }

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'a', 'b', 'c', 'e'},
                {'s', 'f', 'c', 's'},
                {'a', 'd', 'e', 'e'}
        };
        String word = "see";
        LC0079 solver = new LC0079();
        System.out.println(solver.exist(board, word));
    }
}
